package algorithm.linear;

/**
 * 实现算术表达式运算
 */
public class Expression {
    public static void main(String[] args) {
        String expstr = "1*2+3-(4*5-1)";
        String postfix = toPostfix(expstr);
        System.out.println("expstr > "+ expstr);
        System.out.println("postfix > "+ postfix);
        System.out.println("value > "+ value(postfix));
    }
    //转为表达式（中缀、后缀）
    public static String toPostfix(String expstr){
        //只存运算符，如()+-*/
        SeqStack<String> stack = new SeqStack<String>(expstr.length());
        //追加组合表达式
        String postfix = "";
        int i = 0;
        while(i<expstr.length()){
            char ch = expstr.charAt(i);
            switch (ch) {
                case '+':
                case '-':
                    //遇到+、-
                    while (!stack.isEmpty() && !stack.get().equals("(")){
                        postfix += stack.pop();
                    }
                    stack.push(ch+"");
                    i++;
                    break;
                case '*':
                case '/':
                    //遇到*、/
                    while ( !stack.isEmpty() && (stack.get().equals("*")||stack.get().equals("/")) )
                        postfix += stack.pop();
                    stack.push(ch+"");
                    i++;
                    break;
                case '(':
                    //遇到（入栈
                    stack.push(ch+"");
                    i++;
                    break;
                case ')':
                    //遇到）出栈
                    String out = stack.pop().toString();
                    while(out!=null && !out.equals("(")){
                        postfix += out;
                        out = stack.pop().toString();
                    }
                    i++;
                    break;
                default:
                    while(ch >= '0' && ch <= '9') {
                        postfix += ch;
                        i++;
                        if (i < expstr.length()){
                            ch = expstr.charAt(i);
                        } else {
                            ch = '=';
                        }
                    }
                    postfix += " ";
            }
        }
        System.out.println(stack.toString());
        while(!stack.isEmpty()){
            postfix += stack.pop();
        }
        return postfix;
    }

    //计算后缀表达式的值
    public static int value(String postfix) {
        LinkedStack<Integer> stack = new LinkedStack<Integer>();
        int i=0,result=0;
        while( i<postfix.length() ) {
            char ch = postfix.charAt(i);
            if (ch >= '0' && ch <= '9') {
                result = 0;
                //字符串转为数值
                while (ch != ' ') {
                    result = result*10+Integer.parseInt(ch+"");
                    i++;
                    ch = postfix.charAt(i);
                }
                i++;
                stack.push(new Integer(result));
            }
            else {
                int y = stack.pop();
                int x = stack.pop();
                switch (ch) {
                    case '+':result=x+y;break;
                    case '-':result=x-y;break;
                    case '*':result=x*y;break;
                    case '/':result=x/y;break; //整除
                }
                //运算结果入栈
                stack.push(new Integer(result));
                i++;
            }
        }
        return stack.pop();
    }

}
